home *** CD-ROM | disk | FTP | other *** search
/ Aminet 30 / Aminet 30 (1999)(Schatztruhe)[!][Apr 1999].iso / Aminet / dev / lang / SmallEiffel.lha / SmallEiffel / lib_show / pyramid2.e < prev    next >
Text File  |  1998-12-22  |  4KB  |  181 lines
  1. --          This file is part of SmallEiffel The GNU Eiffel Compiler.
  2. --          Copyright (C) 1994-98 LORIA - UHP - CRIN - INRIA - FRANCE
  3. --            Dominique COLNET and Suzanne COLLIN - colnet@loria.fr 
  4. --                       http://www.loria.fr/SmallEiffel
  5. -- SmallEiffel is  free  software;  you can  redistribute it and/or modify it 
  6. -- under the terms of the GNU General Public License as published by the Free
  7. -- Software  Foundation;  either  version  2, or (at your option)  any  later 
  8. -- version. SmallEiffel is distributed in the hope that it will be useful,but
  9. -- WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  10. -- or  FITNESS FOR A PARTICULAR PURPOSE.   See the GNU General Public License 
  11. -- for  more  details.  You  should  have  received a copy of the GNU General 
  12. -- Public  License  along  with  SmallEiffel;  see the file COPYING.  If not,
  13. -- write to the  Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  14. -- Boston, MA 02111-1307, USA.
  15. --
  16. class PYRAMID2
  17. --
  18. --| Auteur : Christophe Alexandre
  19. --|  date  : Tue Feb 27 14:39:12 1996
  20. --|
  21. --| Run faster than pyramid.e   
  22.    
  23. inherit ANY redefine print_on end;
  24.    
  25. creation {ANY}
  26.    make
  27.    
  28. feature {NONE}
  29.    
  30.    pyramid: ARRAY2[INTEGER]; 
  31.    
  32.    used: ARRAY[BOOLEAN]; -- Already used numbers in `pyramid'.
  33.    
  34.    make is
  35.       do
  36.      from
  37.         ask 
  38.      until
  39.         io.last_integer > 1
  40.      loop
  41.         ask;
  42.      end
  43.      io.put_string("I am working...%N");
  44.      fill(io.last_integer);
  45.       end; -- make
  46.    
  47.    ask is
  48.       do
  49.      io.put_string("Size of the pyramid %
  50.             % (a small number greater than 1) : ");
  51.      io.flush;
  52.      io.read_integer;
  53.      io.put_new_line;
  54.       end; -- ask
  55.    
  56.    fill(size : INTEGER) is
  57.      -- Fill in a `pyramid' of `size' elements. 
  58.       require
  59.      size > 1;
  60.       do
  61.      !!used.make(1,(size+1)*size // 2);
  62.      !!pyramid.make(1,size,1,size);
  63.      if solution(1) then
  64.         print_on(std_output)
  65.      else
  66.         io.put_string("Sorry I can't find a solution.%N");
  67.      end;
  68.       end; -- fill
  69.    
  70.    put(value,line,column: INTEGER) is
  71.      -- Updtate `pyramid' and `used'. 
  72.       do
  73.      used.put(true,value);
  74.      pyramid.put(value,line,column);
  75.       end; -- put
  76.    
  77.    remove(line,column :INTEGER) is
  78.      -- Updtate `pyramid' and `used'. 
  79.       do 
  80.      if pyramid.item(line,column) /= 0 then
  81.         used.put(false,pyramid.item(line,column));
  82.         pyramid.put(0,line,column);
  83.      end;
  84.       end; -- remove
  85.    
  86.    solution(column:INTEGER): BOOLEAN is
  87.      -- Search a solution using a back-tracking algorithm.
  88.       local 
  89.      nb,i: INTEGER;
  90.       do
  91.      if column > pyramid.upper1 then
  92.         Result := true;
  93.      else
  94.         from
  95.            nb := used.upper
  96.         until
  97.            Result or nb = 0
  98.         loop
  99.            if not used.item(nb) then
  100.           Result := fill_column(column,nb)
  101.            end;
  102.            if not Result then
  103.           from
  104.              i := pyramid.lower1
  105.           until
  106.              pyramid.item(i,column) = 0 or else i > pyramid.upper1 
  107.           loop
  108.              remove(i,column);
  109.              i := i + 1;
  110.           end;
  111.            end;
  112.            nb := nb - 1;
  113.         end;
  114.      end;
  115.       end; -- solution
  116.    
  117.    fill_column(col,val: INTEGER): BOOLEAN is
  118.       local
  119.      v, i: INTEGER;
  120.       do
  121.      from 
  122.         i := 2;
  123.         put(val,1,col);
  124.      until
  125.         i > col or Result 
  126.      loop
  127.         v := (pyramid.item(i-1,col-1)-pyramid.item(i-1,col)).abs
  128.         if used.item(v) then
  129.            Result := true;
  130.         else
  131.            put(v,i,col);
  132.            i := i+1;
  133.         end;
  134.      end;
  135.      if Result then
  136.         from
  137.         until
  138.            i < used.lower
  139.         loop
  140.            remove(i,col);
  141.            i := i-1;
  142.         end;
  143.         Result := false;
  144.      else
  145.         Result := solution(col+1);
  146.      end;
  147.       end; -- fill_column
  148.    
  149.    print_on(file: OUTPUT_STREAM) is
  150.      -- display the pyramid to the standart output.
  151.       local
  152.      line,column : INTEGER;
  153.      blanks : STRING;
  154.       do
  155.      from
  156.         file.put_string("%NSolution found : %N");
  157.         line := pyramid.lower1;
  158.         !!blanks.make(0);
  159.      until
  160.         line > pyramid.upper1
  161.      loop
  162.         file.put_string(blanks);
  163.         from
  164.            column := pyramid.lower2
  165.         until
  166.            column > pyramid.upper2
  167.         loop
  168.            if pyramid.item(line,column) /= 0 then
  169.           file.put_integer(pyramid.item(line,column));
  170.           file.put_string(" ");
  171.            end;
  172.            column := column+1;
  173.         end;
  174.         file.put_new_line;
  175.         line := line+1;
  176.         blanks.add_last(' ');
  177.      end;   
  178.       end; -- print_on
  179.    
  180. end -- PYRAMID2
  181.